home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / insert.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  8KB  |  314 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)insert.c    5.3 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45. #include "btree.h"
  46. #include "utils.h"
  47.  
  48. /*
  49.  *  _BT_INSERT -- Insert a new user datum in the btree.
  50.  *
  51.  *    This routine is called by bt_put, the public interface, once the
  52.  *    location for the new item is known.  We do the work here, and
  53.  *    handle splits if necessary.
  54.  *
  55.  *    Parameters:
  56.  *        t -- btree in which to do the insertion.
  57.  *        item -- BTITEM describing location of new datum
  58.  *        key -- key to insert
  59.  *        data -- data associated with key
  60.  *        flag -- magic cookie passed recursively to bt_put if we
  61.  *            have to do a split
  62.  *
  63.  *    Returns:
  64.  *        RET_SUCCESS, RET_ERROR.
  65.  */
  66.  
  67. int
  68. _bt_insert(t, item, key, data, flag)
  69.     BTREE_P t;
  70.     BTITEM *item;
  71.     DBT *key;
  72.     DBT *data;
  73.     int flag;
  74. {
  75.     index_t index;
  76.     BTHEADER *h;
  77.     DATUM *d;
  78.     int nbytes;
  79.     int status;
  80.     pgno_t pgno;
  81.     int keysize, datasize;
  82.     int bigkey, bigdata;
  83.  
  84.     if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  85.         return (RET_ERROR);
  86.     h = t->bt_curpage;
  87.  
  88.     if (TOOBIG(t, data->size)) {
  89.         bigdata = TRUE;
  90.         datasize = sizeof(pgno_t);
  91.     } else {
  92.         bigdata = FALSE;
  93.         datasize = data->size;
  94.     }
  95.  
  96.     if (TOOBIG(t, key->size)) {
  97.         bigkey = TRUE;
  98.         keysize = sizeof(pgno_t);
  99.     } else {
  100.         bigkey = FALSE;
  101.         keysize = key->size;
  102.     }
  103.  
  104.     nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
  105.     nbytes = LONGALIGN(nbytes) + sizeof(index_t);
  106.  
  107.     /* if there's not enough room here, split the page */
  108.     if ((h->h_upper - h->h_lower) < nbytes) {
  109.         if (_bt_split(t) == RET_ERROR)
  110.             return (RET_ERROR);
  111.  
  112.         /* okay, try again (empty the stack first, though) */
  113.         while (_bt_pop(t) != P_NONE)
  114.             continue;
  115.  
  116.         return (bt_put((DB *)t, key, data, flag));
  117.     }
  118.  
  119.     /* put together a leaf page datum from the key/data pair */
  120.     index = item->bti_index;
  121.     nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
  122.  
  123.     if ((d = (DATUM *) malloc((unsigned) nbytes)) == (DATUM *) NULL)
  124.         return (RET_ERROR);
  125.  
  126.     d->d_ksize = keysize;
  127.     d->d_dsize = datasize;
  128.     d->d_flags = 0;
  129.  
  130.     if (bigkey) {
  131.         if (_bt_indirect(t, key, &pgno) == RET_ERROR)
  132.             return (RET_ERROR);
  133.         (void) bcopy((char *) &pgno, &(d->d_bytes[0]), sizeof(pgno));
  134.         d->d_flags |= D_BIGKEY;
  135.         if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  136.             return (RET_ERROR);
  137.     } else {
  138.         if (d->d_ksize > 0) {
  139.             (void) bcopy((char *) key->data,
  140.                       (char *) &(d->d_bytes[0]),
  141.                       (int) d->d_ksize);
  142.         }
  143.     }
  144.  
  145.     if (bigdata) {
  146.         if (_bt_indirect(t, data, &pgno) == RET_ERROR)
  147.             return (RET_ERROR);
  148.         (void) bcopy((char *) &pgno,
  149.                  &(d->d_bytes[keysize]),
  150.                  sizeof(pgno));
  151.         d->d_flags |= D_BIGDATA;
  152.         if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  153.             return (RET_ERROR);
  154.     } else {
  155.         if (d->d_dsize > 0) {
  156.             (void) bcopy((char *) data->data,
  157.                       (char *) &(d->d_bytes[keysize]),
  158.                       (int) d->d_dsize);
  159.         }
  160.     }
  161.  
  162.     /* do the insertion */
  163.     status = _bt_insertat(t, (char *) d, index);
  164.  
  165.     (void) free((char *) d);
  166.  
  167.     return (status);
  168. }
  169.  
  170. /*
  171.  *  _BT_INSERTI -- Insert IDATUM on current page in the btree.
  172.  *
  173.  *    This routine handles insertions to internal pages after splits
  174.  *    lower in the tree.  On entry, t->bt_curpage is the page to get
  175.  *    the new IDATUM.  We are also given pgno, the page number of the
  176.  *    IDATUM that is immediately left of the new IDATUM's position.
  177.  *    This guarantees that the IDATUM for the right half of the page
  178.  *    after a split goes next to the IDATUM for its left half.
  179.  *
  180.  *    Parameters:
  181.  *        t -- tree in which to do insertion.
  182.  *        id -- new IDATUM to insert
  183.  *        pgno -- page number of IDATUM left of id's position
  184.  *
  185.  *    Returns:
  186.  *        RET_SUCCESS, RET_ERROR.
  187.  */
  188.  
  189. int
  190. _bt_inserti(t, id, pgno)
  191.     BTREE_P t;
  192.     IDATUM *id;
  193.     pgno_t pgno;
  194. {
  195.     BTHEADER *h = t->bt_curpage;
  196.     index_t next, i;
  197.     IDATUM *idx;
  198.     char *key;
  199.     pgno_t chain;
  200.     int free_key;
  201.     int ignore;
  202.  
  203.     if (id->i_flags & D_BIGKEY) {
  204.         free_key = TRUE;
  205.         bcopy(&(id->i_bytes[0]), (char *) &chain, sizeof(chain));
  206.         if (_bt_getbig(t, chain, &key, &ignore) == RET_ERROR)
  207.             return (RET_ERROR);
  208.     } else {
  209.         free_key = FALSE;
  210.         key = &(id->i_bytes[0]);
  211.     }
  212.     i = _bt_binsrch(t, key);
  213.  
  214.     next = NEXTINDEX(h);
  215.     while (i < next && _bt_cmp(t, key, i) >= 0)
  216.         i++;
  217.  
  218.     if (free_key)
  219.         (void) free(key);
  220.  
  221.     /* okay, now we're close; find adjacent IDATUM */
  222.     for (;;) {
  223.         idx = (IDATUM *) GETDATUM(h,i);
  224.         if (idx->i_pgno == pgno) {
  225.             i++;
  226.             break;
  227.         }
  228.         --i;
  229.     }
  230.  
  231.     /* correctly positioned, do the insertion */
  232.     return (_bt_insertat(t, (char *) id, i));
  233. }
  234.  
  235. /*
  236.  *  _BT_INSERTAT -- Insert a datum at a given location on the current page.
  237.  *
  238.  *    This routine does insertions on both leaf and internal pages.
  239.  *
  240.  *    Parameters:
  241.  *        t -- tree in which to do insertion.
  242.  *        p -- DATUM or IDATUM to insert.
  243.  *        index -- index in line pointer array to put this item.
  244.  *
  245.  *    Returns:
  246.  *        RET_SUCCESS, RET_ERROR.
  247.  *
  248.  *    Side Effects:
  249.  *        Will rearrange line pointers to make space for the new
  250.  *        entry.  This means that any scans currently active are
  251.  *        invalid after this.
  252.  *
  253.  *    Warnings:
  254.  *        There must be sufficient room for the new item on the page.
  255.  */
  256.  
  257. int
  258. _bt_insertat(t, p, index)
  259.     BTREE_P t;
  260.     char *p;
  261.     index_t index;
  262. {
  263.     IDATUM *id = (IDATUM *) p;
  264.     DATUM *d = (DATUM *) p;
  265.     BTHEADER *h;
  266.     CURSOR *c;
  267.     index_t nxtindex;
  268.     char *src, *dest;
  269.     int nbytes;
  270.  
  271.     /* insertion may confuse an active scan.  fix it. */
  272.     c = &(t->bt_cursor);
  273.     if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
  274.         if (_bt_fixscan(t, index, d, INSERT) == RET_ERROR)
  275.             return (RET_ERROR);
  276.  
  277.     h = t->bt_curpage;
  278.     nxtindex = (index_t) NEXTINDEX(h);
  279.  
  280.     /*
  281.      *  If we're inserting at the middle of the line pointer array,
  282.      *  copy pointers that will follow the new one up on the page.
  283.      */
  284.  
  285.     if (index < nxtindex) {
  286.         src = (char *) &(h->h_linp[index]);
  287.         dest = (char *) &(h->h_linp[index + 1]);
  288.         nbytes = (h->h_lower - (src - ((char *) h)))
  289.              + sizeof(h->h_linp[0]);
  290.         (void) bcopy(src, dest, nbytes);
  291.     }
  292.  
  293.     /* compute size and copy data to page */
  294.     if (h->h_flags & F_LEAF) {
  295.         nbytes = d->d_ksize + d->d_dsize
  296.              + (sizeof(DATUM) - sizeof(char));
  297.     } else {
  298.         nbytes = id->i_size + (sizeof(IDATUM) - sizeof(char));
  299.     }
  300.     dest = (((char *) h) + h->h_upper) - LONGALIGN(nbytes);
  301.     (void) bcopy((char *) p, dest, nbytes);
  302.  
  303.     /* update statistics */
  304.     dest -= (int) h;
  305.     h->h_linp[index] = (index_t) dest;
  306.     h->h_upper = (index_t) dest;
  307.     h->h_lower += sizeof(index_t);
  308.  
  309.     /* we're done */
  310.     h->h_flags |= F_DIRTY;
  311.  
  312.     return (RET_SUCCESS);
  313. }
  314.